package LeetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LC_658_FindKClosestElements {

    public static void main(String[] args) {

    }

    public class Solution {
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            List<Integer> list = new ArrayList<>();
            for (int anArr : arr) list.add(anArr);
            int n = list.size();
            if (x <= list.get(0)) {
                return list.subList(0, k);
            } else if (list.get(n - 1) <= x) {
                return list.subList(n - k, n);
            } else {
                int index = Collections.binarySearch(list, x);
                if (index < 0)
                    index = -index - 1;
                int low = Math.max(0, index - k - 1), high = Math.min(list.size() - 1, index + k - 1);
                while (high - low > k - 1) {
                    if (low < 0 || (x - list.get(low)) <= (list.get(high) - x))
                        high--;
                    else if (high > list.size() - 1 || (x - list.get(low)) > (list.get(high) - x))
                        low++;
                    else
                        System.out.println("unhandled case: " + low + " " + high);
                }
                return list.subList(low, high + 1);
            }
        }
    }

}